数学作业

Time Limit: 10 Sec Memory Limit: 128 MB

Description

img

Input

输入文件只有一行为用空格隔开的两个正整数N和M。

Output

输出仅包含一个非负整数，表示Concatenate(1~N) MOD M的值。

Sample Input

12345678910 1000000000

Sample Output

345678910

HINT

1<=N<=10^8 , 1<=M<=10^9

Main idea

给定一个n,m，创造一个数字顺序连接1~n，输出这个数对m取模的值。

Solution

n<=10^18，排除找规律的可能性，立马想到了用矩阵乘法优化DP，令f[i]表示1~i的值，那么：

img

然后我们只要推出矩阵即可，轻松想到了：

img

然后分段矩乘得到答案。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;

const int ONE=5;

long long n,MOD;
long long a[ONE][ONE],b[ONE][ONE];
long long Index;


void Mul(long long a[ONE][ONE],long long b[ONE][ONE],long long ans[ONE][ONE])
{
    long long jilu[ONE][ONE];
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
        {
            jilu[i][j]=0;
            for(int k=1;k<=3;k++)
                jilu[i][j]=(jilu[i][j] + a[i][k]*b[k][j]%MOD) % MOD;
        }

    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            ans[i][j]=jilu[i][j];
}

void Matrix(long long a[ONE][ONE],long long b[ONE][ONE],long long t)
{
    while(t)
    {
        if(t&1) Mul(a,b,a);
        Mul(b,b,b);
        t>>=1;
    }
}

int main()
{
    cin>>n>>MOD;
    a[1][3]=1;

    long long len=1;
    for(;;)
    {
        len*=10;
        memset(b,0,sizeof(b));
        for(int i=1;i<=3;i++)
        {
            for(int j=1;j<=i;j++)
                b[i][j]=1;
        }
        b[1][1]=len % MOD;

        if(len<=n) Index=len-len/10;
        else Index=n-len/10+1;
        Matrix(a,b,Index);
        if(len>n) break;
    }

    printf("%lld",a[1][1]);
}